//
// Created by Panfeng Guo on 2022/11/13.
//
#include <sstream>

#include "common/exception.h"
#include "common/rid.h"
#include "common/logger.h"
#include "storage/page/b_plus_tree_leaf_page.h"
#include "storage/page/b_plus_tree_internal_page.h"

/*!
 * Insert: insert a kv into leaf node and keep kv in order
 * only unique key are supported
 * @tparam KeyType
 * @tparam ValueType
 * @tparam KeyComparator
 * @param key: key must be unique
 * @param value
 * @param comparator
 * @return: the size of leaf node after insertion
 */
template <typename KeyType, typename ValueType, typename KeyComparator>
int BPlusTreeLeafPage<KeyType, ValueType, KeyComparator>::
Insert(const KeyType &key, const ValueType &value, const KeyComparator &comparator)
{
    if (GetSize() == 0 || comparator(key, KeyAt(GetSize() - 1)) > 0) { // case 1: insert value is maximum
        array[GetSize()] = {key, value};
    }else if (comparator(key, array[0].first) < 0) { // case 2: insert value is minimum
        memmove(array + 1, array, GetSize() * sizeof(MappingType));
        array[0] = {key, value};
    }else{ // case 3: insert middle
        // binary search
        int left = 0, right = GetSize() - 1, mid;
        while (left < right && left + 1 != right)
        {
            mid = left + (right - left) / 2;
            if (comparator(key, array[mid].first) < 0){
                right = mid;
            }else if (comparator(key, array[mid].first) > 0){
                left = mid;
            }else{
                // only support unique key
                assert(0);
            }
        }
        memmove(array + right + 1, array + right,(GetSize() - right) * sizeof(MappingType));
        array[right] = {key, value};
    }
    IncreaseSize(1);
    assert(GetSize() <= GetMaxSize());
    return GetSize();
}

/*!
 * MoveHalfTo: move half of page to recipient page
 * @tparam KeyType
 * @tparam ValueType
 * @tparam KeyComparator
 * @param recipient: the target page to move
 * @param buffer_pool_manager
 */
template <typename KeyType, typename ValueType, typename KeyComparator>
void BPlusTreeLeafPage<KeyType, ValueType, KeyComparator>::
MoveHalfTo(BPlusTreeLeafPage *recipient,
           __attribute__((unused)) BufferPoolManager *buffer_pool_manager)
{
    // step 1: copy half into recipient page
    assert(GetSize() > 0);
    int size = GetSize() / 2;
    MappingType *src = array + GetSize() - size;
    recipient->CopyFrom(src, size);
    // step 2: reduce the original page size
    IncreaseSize(-1 * size);
}

/*!
 * CopyFrom: copy from items
 * @tparam KeyType
 * @tparam ValueType
 * @tparam KeyComparator
 * @param items: the item copying from
 * @param size: the size to copy
 */
template <typename KeyType, typename ValueType, typename KeyComparator>
void BPlusTreeLeafPage<KeyType, ValueType, KeyComparator>::
CopyFrom(MappingType *items, int size)
{
    assert(GetSize() + size <= GetMaxSize());
    int start = GetSize();
    for (int i = 0; i < size; ++i){
        array[start+i] = *items++;
    }
    IncreaseSize(size);
}

template <typename KeyType, typename ValueType, typename KeyComparator>
bool BPlusTreeLeafPage<KeyType, ValueType, KeyComparator>::
Lookup(const KeyType &key, ValueType &value,
       const KeyComparator &comparator) const
{
    if (GetSize() == 0 || comparator(key, KeyAt(0)) < 0 ||
        comparator(key, KeyAt(GetSize() - 1)) > 0){ // case 1:key out of range
        return false;
    }else { // case 2: key in the range
        // binary search
        int left = 0, right = GetSize() - 1, mid;
        while (left <= right) {
            mid = left + (right - left) / 2;
            if (comparator(key, KeyAt(mid)) > 0) {
                left = mid + 1;
            } else if (comparator(key, KeyAt(mid)) < 0) {
                right = mid - 1;
            } else {
                value = array[mid].second;
                return true;
            }
        }
        return false;
    }
}

/*****************************************************************************
 * Helper method to get and set value
 *****************************************************************************/
template <typename KeyType, typename ValueType, typename KeyComparator>
void BPlusTreeLeafPage<KeyType, ValueType, KeyComparator>::
Init(page_id_t page_id, page_id_t parent_id)
{
    // step 1: cal max_size
    int size = (PAGE_SIZE - sizeof(BPlusTreeLeafPage)) / (sizeof(KeyType) + sizeof(ValueType));
    // step 2: set value
    SetPageType(IndexPageType::LEAF_PAGE);
    SetSize(0);
    SetPageId(page_id);
    SetParentPageId(parent_id);
    SetNextPageId(INVALID_PAGE_ID);
    SetMaxSize(size);
}

template <typename KeyType, typename ValueType, typename KeyComparator>
page_id_t BPlusTreeLeafPage<KeyType, ValueType, KeyComparator>::
GetNextPageId() const
{
    return next_page_id_;
}

template <typename KeyType, typename ValueType, typename KeyComparator>
void BPlusTreeLeafPage<KeyType, ValueType, KeyComparator>::
SetNextPageId(page_id_t next_page_id)
{
    next_page_id_ = next_page_id;
}

template <typename KeyType, typename ValueType, typename KeyComparator>
int BPlusTreeLeafPage<KeyType, ValueType, KeyComparator>::
KeyIndex(const KeyType &key, const KeyComparator &comparator) const
{
    for (int i = 0; i < GetSize(); ++i)
    {
        if (comparator(key, array[i].first) <= 0)
        {
            return i;
        }
    }
    return GetSize();
}

template <typename KeyType, typename ValueType, typename KeyComparator>
KeyType BPlusTreeLeafPage<KeyType, ValueType, KeyComparator>::
KeyAt(int index) const
{
    // replace with your own code
    assert(0 <= index && index < GetSize());
    return array[index].first;
}

template <typename KeyType, typename ValueType, typename KeyComparator>
const MappingType &BPlusTreeLeafPage<KeyType, ValueType, KeyComparator>::
GetItem(int index)
{
    // replace with your own code
    assert(0 <= index && index < GetSize());
    return array[index];
}
